package com.lw.leetcode.str.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 2468. 根据限制分割消息
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/17 9:57
 */
public class SplitMessage {


    public static void main(String[] args) {
        SplitMessage test = new SplitMessage();

        // [...,"ge<14/14>"]
//        String str = "this is really a very awesome message";
//        int limit = 9;

        // [...,"age<2/2>"]
//        String str = "short message";
//        int limit = 15;

        // ["abb<1/7>","aba<2/7>","bbb<3/7>","aaa<4/7>"," aa<5/7>","baa<6/7>"," a<7/7>"]
//        String str = "abbababbbaaa aabaa a";
//        int limit = 2;

        // ["hello<1/3>"," worl<2/3>","d<3/3>"]
        String str = "hello world";
        int limit = 10;

//        String str = Utils.getStr(10000, 'a', 'z');
//        int limit = 12;
//        System.out.println(limit);

        String[] strings = test.splitMessage(str, limit);
        System.out.println(Arrays.toString(strings));
    }

    public String[] splitMessage(String message, int limit) {
        int count = find(message.length(), limit);
        if (count == -1) {
            return new String[0];
        }
        String temp = "/" + count + ">";
        int step = limit - temp.length() - 2;
        String[] arr = new String[count];
        int item = 0;
        int next = 9;
        int sum = 0;
        while (next < count) {
            for (int i = item + 1; i <= next; i++) {
                arr[i - 1] = message.substring(sum, step + sum) + "<" + i + temp;
                sum += step;
            }
            step--;
            item = next;
            next = item * 10 + 9;
        }
        for (int i = item + 1; i < count; i++) {
            arr[i - 1] = message.substring(sum, step + sum) + "<" + i + temp;
            sum += step;
        }
        arr[count - 1] = message.substring(sum) + "<" + count + temp;
        return arr;
    }

    private int find(int length, int count, int limit) {
        int step = limit - String.valueOf(count).length() - 4;
        int item = 0;
        int next = 9;
        int sum = 0;
        while (next < count) {
            sum += (next - item) * step;
            step--;
            item = next;
            next = item * 10 + 9;
        }
        int min = sum + (count - item - 1) * step;
        int max = sum + (count - item) * step;
        if (length <= min) {
            return 1;
        }
        if (length > max) {
            return 2;
        }
        return 0;
    }

    private int find(int length, int limit) {
        int st = 0;
        int end = length;
        int s = 10;
        while (s < 10000) {
            int v = find(length, s - 1, limit);
            if (v == 0) {
                return s - 1;
            } else if (v == 1) {
                end = s - 1;
                st = s / 10;
                break;
            }
            s *= 10;
        }
        while (st <= end) {
            int m = st + ((end - st) >> 1);
            int v = find(length, m, limit);
            if (v == 0) {
                return m;
            } else if (v == 1) {
                end = m - 1;
            } else {
                st = m + 1;
            }
        }
        return -1;
    }

}
